#include <iostream>
#include <climits>
#define NIL -1
struct Node{
int to, weight;
Node* next=nullptr;
Node(int _to, int _weight): to(_to), weight(_weight) {}
};
struct Vertex{
int d=INT_MAX, pi=NIL;
Vertex(){}
};
struct adjList{
int nV, nE;
Node** list;
Vertex* vertex;
adjList(int _nV, int _nE): nV(_nV), nE(_nE){
this->list=new Node*[this->nV];
this->vertex=new Vertex[this->nV];
}
~adjList(){
for(int i=0; i<this->nV; ++i) delete list[i];
delete[] list;
delete[] vertex;
}
void Insert(int u, int v, int weight){
Node* nN=new Node(v, weight);
Node* cur=this->list[u-1];
if(cur==nullptr){
list[u-1]=nN;
} else {
while(cur->next!=nullptr) cur=cur->next;
cur->next=nN;
}
}
int Weight(int u, int v){
Node* cur=this->list[u-1];
while(cur!=nullptr && cur->to!=v) cur=cur->next;
return cur->weight;
}
void InitializeSingleSource(int s){
for(int i=0; i<this->nV; ++i){
this->vertex[i].d=INT_MAX;
this->vertex[i].pi=NIL;
}
this->vertex[s-1].d=0;
}
void Relax(int u, int v){
int* Vd=&(this->vertex[v-1].d);
int weightUV=Weight(u, v), Ud=this->vertex[u-1].d;
if(*Vd==INT_MAX && Ud==INT_MAX) return;
if(*Vd>Ud+weightUV){
*Vd=Ud+weightUV;
vertex[v-1].pi=u;
}
}
};
bool BellmanFord(adjList* G, int s){
G->InitializeSingleSource(s);
for(int i=0; i<G->nV-1; ++i){
for(int u=1; u<G->nV+1; ++u){
Node* cur=G->list[u-1];
if(cur==nullptr) continue;
while(cur!=nullptr){
int v=cur->to;
G->Relax(u, v);
cur=cur->next;
}
}
}
for(int u=1; u<G->nV+1; ++u){
Node* cur=G->list[u-1];
if(cur==nullptr) continue;
while(cur!=nullptr){
int v=cur->to;
if(G->vertex[v-1].d>G->vertex[u-1].d+G->Weight(u, v)) return false;
cur=cur->next;
}
}
return true;
}
int main(void){
int vN=5, vE=10;
adjList* Graph=new adjList(vN, vE);
int eg[][3]={
{1, 2, 6}, {1, 4, 7}, {2, 3, 5}, {2, 4, 8}, {2, 5, -4},
{3, 2, -2}, {4, 3, -3}, {4, 5, 9}, {5, 1, 2}, {5, 3, 7}
};
for(int i=0; i<vE; ++i){
Graph->Insert(eg[i][0], eg[i][1], eg[i][2]);
}
bool isroute=BellmanFord(Graph, 1);
std::cout<<isroute<<std::endl;
delete Graph;
return 0;
}